package hashTable;

import org.junit.Test;

import java.util.HashMap;
import java.util.Map;

/**
 * @Description 1. 两数之和  https://leetcode.cn/problems/two-sum/
 * @Author Firenut
 * @Date 2023-02-19 00:47
 */
public class T1_twoSum {
    @Test
    public void test() {
        twoSum(new int[]{3, 2, 4}, 6);
    }

    // 目的是找到两个数之和为target嘛
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        // 先不急着put进去,而是每次遍历看看是否存在,
        // 遍历每一个元素前都没有将其加入hash表,这样就不会出现   当 target - nums[i] == nums[i] 时 map.containsKey(target - nums[i])为true的情况
        // 虽然2，4是答案，当遍历2的时候计算得到的4不在hash表中，所以存入2
        // 后续遍历到4的时候就可以从hah表中找到2，从而返回答案(它两互补嘛)
        for (int i = 0; i < nums.length; i++) {
            int other = target - nums[i];
            if (map.containsKey(other)) { // 如果target - nums[i]存在于哈希表中,可以直接返回,不需要将nums[i]存进hash表
                return new int[]{i, map.get(other)};
            }else{ // 如果target - nums[i]不存在于哈希表中,
                map.put(nums[i],i);
            }
        }
        return new int[]{};
    }
    // 错误的思路: 出现重复的问题
    public int[] error_twoSum1(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            map.put(nums[i], i);
        }

        // 注意有个去重的问题,比如target为6, 数组为:[3,2,4]的情况,
        // map.containsKey(target - 3)得到的key还是3,肯定存在于hash表，所以出现重复了
        for (int i = 0; i < nums.length; i++) {
            int other = target - nums[i];
            if (map.containsKey(other)) {
                return new int[]{i, map.get(other)};
            }
        }
        return new int[]{};
    }
}
